\documentclass[11pt,twoside,a4paper]{article}

%\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
%\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
\usepackage{algorithmic}
\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\C}{\mathbb{C}} % les complexes
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_{\K}}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\Nm}{\mathcal{N}}
\newcommand{\ag}{\mathfrak{a}}
\newcommand{\bg}{\mathfrak{b}}
\newcommand{\cg}{\mathfrak{c}}
\newcommand{\dg}{\mathfrak{d}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\add}{\alpha_{d,\Delta , \gamma}}
\newcommand{\bdd}{\beta_{d,\Delta , \gamma}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{A polynomial time algorithm for computing an HNF basis of an $\OK$-module and its applications
to coding theory.}
\author{Jean-Fran\c{c}ois Biasse\\Claus Fieker\\Guillaume Quintin}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières

\begin{abstract}
We present a variation of the modular algorithm for computing the pseudo-HNF of an $\OK$-module presented 
in~\cite{cohen2}. The modular strategy was conjectured to run in polynomial time by Cohen, but so far, 
no such proof was available in the litterature. We apply this result to list-decode codewords of algebraic number field codes in polynomial time up to the Johnson bound. This is the first explicit procedure for decoding number field codes whose construction were previously described by 
Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}.
\end{abstract}

\section{Introduction}

The construction of a good basis of an $\OK$-module, where $K$ is a number field and $\OK$ its ring of 
integers, has recently received a growing interest from the cryptographic community. Indeed, $\OK$-modules 
occur in lattice-based cryptography~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, where 
cryptosystems rely on the difficulty to find the shortest element of a module, or solving the closest 
vector problem. The computation of a good basis is crucial for solving these problems, and most of the 
algorithms for computing a reduced basis of a $\Z$-lattice have an equivalent for $\OK$-modules. However, 
applying the available tools over $\Z$ to $\OK$-modules would result in the loss of of their structure. 

The computation of a Hermite Normal Form (HNF)-basis was generalized to $\OK$-modules by Cohen~\cite[Chap. 1]{cohen2}. 
His algorithm returns a basis that enjoys similar properties as the HNF of a $\Z$-module. A 
modular version of this algorithm is conjectured to run in polynomial time, although this statement is not 
proven (see last remark of~\cite[1.6.1]{cohen2}). In addition, Fieker and Stehl{\'e}'s recent algorithm for computing a 
sized-reduced basis relies on the conjectured possibility to compute an HNF-basis for an $\OK$-module in polynomial 
time~\cite[Th. 1]{stehle_fieker_LLL}. This allows a polynomial time equivalent of the LLL algorithm preserving the 
structure of $\OK$-module. In this paper, we adress the problem of the polynomiality of the computation of an 
HNF basis for an $\OK$-module by presenting a modified version of Cohen's algorithm~\cite[Chap. 1]{cohen2}. We 
thus assure the validity of the LLL algorithm for $\OK$-modules of Fieker and Stehl{\'e}~\cite{stehle_fieker_LLL} which 
has applications in lattice-based cryptography, as well as in representations of matrix groups~\cite{fieker_rep} and 
in automorphism algebras of Abelian varieties. 

Finding a good basis of an $\OK$-module can also be applied in the context of coding theory. Guruswami~\cite[Chap. 7]{guruswami_phd} 
presented a general framework for list-decoding codewords encapsulating Reed-Solomon codes, algebraic-geometric codes, as well as 
the CRT codes and number fields codes. Unlike the others, the latters ,which were independantly presented by 
Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}, do not have a polynomial-time decoding algorithm. As 
we show in this paper, a straightforward adapation of Boneh's algorithm~\cite{Boneh} for decoding CRT codes, combined with 
an ideal-oriented version of Coppersmith algorithm due to Cohn and Heninger~\cite{Coppersmith} allows to present a 
polynomial time decoding algorithm for number field codes. However, this approach does not permit to reach Johnson's bound, 
which ensures that the number of candidates in the code returned for each attempt to decode a message is manageable. On the 
other hand, our approach, that uses a polynomial time algorithm for computing a reduced basis of an $\OK$-module, allows to 
reach the Johnson's bound for number field codes.

\subsubsection*{Our contribution} 

We present in this paper the first polynomial time algorithm for computing an HNF basis of an $\OK$ module based on the modular 
approach of Cohen~\cite[Chap. 1]{cohen2}. We rigorously adress its correctness and derive bounds on its run time. We 
apply this result to list decoding number field codes by following Guruswami's general framework~\cite[Chap. 7]{guruswami_phd}, 
thus achieving a polynomial time algorithm for list decoding these codes up to the Johnson's bound.   

\section{Generalities on number fields}

Let $K$ be a number field of degree $d$. It has $r_1\leq d$ real embeddings $(\sigma_i)_{i\leq r_1}$ and $2r_2$ complex 
embeddings $(\sigma_i)_{r_1 < i \leq 2r_2}$ (coming as $r_2$ pairs of conjugates). The field $K$ is isomorphic to 
$\OK\otimes\Q$ where $\OK$ denotes the ring of integers of $K$. We can embed $K$ in 
$$K_\R := K\otimes \R \simeq \R^{r_1}\times \C^{r_2}, $$ 
and extend the $\sigma_i$'s to $K_\R$. Let $T_2$ be the Hermitian form on $K_\R$ defined by 
$$T_2(x,x') := \sum_i \sigma_i(x)\overline{\sigma_i}(x'),$$
and let $\| x\| := \sqrt{T_2(x,x)}$ be the corresponding $L_2$-norm. Let $(\alpha_i)_{i\leq d}$ such that 
$\OK = \oplus_i \Z\alpha_i$, then the discriminant of $K$ is given by $\Delta = \det^2(T_2(\alpha_i,\alpha_j))$. 
The norm of an element $x\in K$ is defined by $\Nm(x) = \prod_i|\sigma_i(x)|$.

In the context of number field codes, the messages are encoded via their residues modulo prime ideals of $\OK$. For decoding, 
we need a more general notion of ideal, namely the fractional ideals of $\OK$. They can be defined as finitely generated 
$\OK$-modules of $K$. When a fractional ideal is contained in $\OK$, we refer to it as an integral ideal, which is in 
fact an ideal of $\OK$. For every fractional ideal $I$ of $\OK$, there exists $r\in\Z$ such that $rI$ is integral. 
The sum and product of two fractional ideals of $\OK$ is given by 
\begin{align*}
IJ &= \{ i_1j_1 + \cdots + i_lj_l\mid l\in \N, i_1,\cdots i_l\in I, j_1,\cdots j_l\in J\}\\
I + J &= \{ i + j\mid i\in I , j\in J\}.
\end{align*}
The fractional ideals of $\OK$ are invertible, that is for every fractional ideal $I$, there exists 
$I^{-1}:= \{ x\in K\mid xI\subseteq \OK\}$ such that $II^{-1} = \OK$. The set of fractional ideals is equipped with a 
norm function defined by $\Nm(I) = \det(I)/\det(\OK)$. The norm of ideals is multiplicative, and in the case of an 
integral ideal, we have $\Nm(I) = |\OK / I|$. Also note that the norm of $x\in K$ is precisely the norm of the principal 
ideal $(x) = x\OK$. Algorithms for ideal arithmetic in polynomial time in the bit size of $\Delta$ are extensively described 
in~\cite{cohen}.



\section{The HNF}

Let $M\subseteq K^l$ be a finitely generated $\OK$-module. As in~\cite[Chap. 1]{cohen2}, we say that 
$[(a_i),(\mathfrak{a}_i)]_{i\leq n}$, where $a_i\in K$ and $\mathfrak{a}_i$ is a fractional ideal, is a 
pseudo-basis for $M$ if
$$M = \mathfrak{a}_1a_1\oplus \cdots \oplus \mathfrak{a}_na_n.$$
Note that a pseudo-basis is not unique, and the main result of~\cite{stehle_fieker_LLL} is precisely to compute a 
pseudo-basis of short elements. If the sum is not direct, we call $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ a pseudo-generating 
set for $M$. Once a pseudo-generating set $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ for $M$ is known, we can associate a 
pseudo-matrix $A = (A,I)$ to $M$, where $A\in K^{n\times l}$ and $I = (\ag_i)_{i\leq n}$ is a list of $n$ fractional 
ideals such that 
$$M = \ag_1 A_1 + \cdots +\ag_n A_n,$$
where $A_i\in K^l$ is the $i$-th row of $A$. We can construct a pseudo-basis from a pseudo-generating set by using 
the Hermite normal form (HNF) over Dedekind domains (see ~\cite[Th. 1.4.6]{cohen2}). Assume $A$ is of rank $l$ 
(in particular $n\geq l$), then there exists an $n\times n$ matrix $U = (u_{i,j})$ and $n$ non-zero 
ideals $\bg_1, \cdots , \bg_n$ satisfying 
\begin{enumerate}
 \item $\forall i,j, u_{i,j}\in \bg_i^{-1}\ag_j$.
 \item $\ag = \det(U)\bg$ for $\ag = \prod_i\ag_i$ and $\bg = \prod_i \bg_i$.
 \item The matrix $UA$ is of the form\\
\[ UA = \left( 
   \begin{BMAT}(@)[0.5pt,2cm,2cm]{c}{c.c}
   \begin{BMAT}(e)[1pt,1cm,1cm]{cccc}{cccc}
1      & 0      & \hdots & 0      \\
\vdots & 1      & \ddots & \vdots \\
\vdots & \vdots & \ddots & 0      \\
*      & *      & \hdots & 1\\
  \end{BMAT} \\
\begin{BMAT}[0.5pt,1cm,1cm]{c}{c} 
        (0)
\end{BMAT}
\end{BMAT}
   \right).
\]

 \item $M = \bg_{1}\omega_1\oplus \cdots \oplus \bg_{l}\omega_l$ where $\omega_1,\cdots \omega_l$ are the first $l$ rows of $UA$.
\end{enumerate}

In general, the algorithm of~\cite{cohen2} for computing the HNF of a pseudo-matrix takes exponential time, 
but as in the integer case, there exists a modular one which is polynomial in the dimensions of $A$, the 
degree of $K$, and the bit size of the modulo. Note that in the case of a pseudo matrix representing an 
$\OK$-module $M$, the modulo is an integral multiple of the determinantal ideal $\g(M)$, which is generated 
by all the ideals of the form 
$$\det_{i_1,\cdots,i_l}(A)\cdot \ag_{i_1}\cdots\ag_{i_l},$$
where $\det_{i_1,\cdots,i_l}(A)$ is the determinant of the $l\times l$ minor consisting of the last $l$ columns 
of rows of indices $i_1,\cdots,i_l$. The determinantal ideal is a rather involved structure, except in the case $l = n$.

\section{Notion of size}

To ensure that our algorithm for computing an HNF basis of an $\OK$ module runs in polynomial time, we need a notion 
of size %To measure the size of an element $x\in K$, we usually take the bit size of
%$$T_2(x) := |\sigma_1(x)|^2 + \cdots + |\sigma_d(x)|^2,$$
%where $\sigma_1,\cdots,\sigma_d$ are the $d$ complex embeddings of $K$. On the other hand, the size of an ideal usually 
%relates to its norm. We choose a notion of size 
that bounds the bit size required to represent our elements. An ideal 
$I\subset \OK$ is given by the matrix $M^I\in\Z^{d\times d}$ of its basis expressed in an integral basis 
$\omega_1,\cdots,\omega_d$ of $\OK$. If the matrix is in Hermite Normal Form, the size required to store it is therfore bounded by 
$d^2\max_{i,j}\log(|M^I_{i,j}|)$, where $\log(x)$ is the base 2 logarithm of $x$. In the meantime, every coefficient of 
$M^I$ is bounded by $|\det(M^I)|=\Nm(I)$ (see~\cite[Prop. 4.7.4]{cohen}). Thus, we define the size of an ideal as 
$$S(I):= d^2\log(\Nm(I)).$$	
If $\ag = (1/k)I$ is a fractional ideal of $K$, where $I\subset\OK$ and $k\in\Z_{>0}$, then the natural 
generalization of the notion of size is 
$$S(\ag) := \log(k) + S(I),$$
where $\log(k)$ is the base 2 logarithm of $k$.	We also define the size of elements of $K$. If $x\in\OK$ can be written as 
$x = \sum_{i\leq d}x_i\omega_i$, 
where $x_i\in\Z$, then we define its size by 
$$S(x) := d\log(\max_i|x_i|).$$
%$$S(x) := \sum_{i\leq d}\log(|x_i|).$$
It can be generalized to elements $y\in K$ by writing $y = x/k$ where $x\in\OK$ and $k$ is a minimal positive integer, and setting 
$$S(y) := \log(k) + S(x).$$
In the litterature, the size of elements of $K$ is often expressed with $\sqrt{T_2(x)}$. These two notions are in fact 
related.

\begin{proposition}
Let $x\in\OK$, the size of $x$ and its $T_2$-norm satisfy
\begin{align*}
\log\left(\sqrt{T_2(x)}\right)&\leq S(x)+ \log\left(d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}\right)\\
S(x)&\leq d\log\left(2^{3d/2}\sqrt{T_2(x)}\right).
\end{align*}
\end{proposition}

\begin{proof}
Let us show how $S(x)$ and $\log(\sqrt{T_2(x)})$ are 
related. First, we can assume~\cite[Lem. 1]{stehle_fieker_LLL} that we choose an LLL-reduced integral basis 
$\omega_1,\cdots, \omega_d$ of $\OK$ satisfying 
$$\max_i\sqrt{T_2(\omega_i)}\leq \sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}.$$
Then, we have 
\begin{align*}
\forall i\leq d, |x|_i &= |\sigma_i(x)|\\
&= \left| \sum_{j\leq d} |x_j| \sigma_i(\omega_j)\right|\\
&\leq d\left(\max_i |x_i|\right) \left( \max_j\sqrt{T_2(\omega_j)} \right) 
\leq \left(\max_i |x_i|\right) d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.
%&\leq S(x) \frac{2^{d^2/2}\sqrt{|\Delta_K|}}{\sqrt{d}}.
\end{align*}
Therefore, $\log\left(\sqrt{T_2(x)}\right)\leq S(x)+ \log\left(d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}\right)$. On the other hand, we know from~\cite[Lem. 2]{stehle_fieker_LLL} that for our choice of an integral basis 
of $\OK$, we have
%the 
%arithmetic-geometric inequality tells us that 
$$\forall x\in\OK, \ S(x)\leq d\log\left(2^{3d/2}\sqrt{T_2(x)}\right).$$
\end{proof}

So, for all $x\in \OK$, 
$S(x) = O\left(\log\left( \sqrt{T_2(x)}\right)\right)$, and $\log\left( \sqrt{T_2(x)}\right) = O(S(x))$, 
where the constants are polynomial in $d$ and $\log|\Delta_K|$. This still holds when $x\in K$. 

\section{The normalization}

Given a one-dimensional $\OK$-module $\ag A\subseteq\OK^n$ where $\ag$ is a fractional ideal of $K$, and $A\in K^n$, it is 
interesting to find $b\in K$ such that the size taken to represent our module as $(b\ag)(A/b)$ is bounded 
by reasonable values. Indeed, the same module can be represented by elements of arbitrary large size, which 
would cause a significant slow-down in our algorithms.

The first step to our normalization is to make sure that $\ag$ is integral. If $k\in\Z$ is its denominator,
then replacing $\ag$ by $k\ag$ and $A$ by $A/k$ increases the size needed to represent our module via the 
growth of all the denominator of the coefficients of $A\in K^n$. This growth is of 
$$n\log(k).$$ 

We can now assume that our one-dimensional module is of the form $\ag A$ where $\ag\subseteq\OK$ and 
$A\in K^n$ at the price of a slight growth of its size. The next step of normalization is to express our 
module as $\ag' A'$ where $A'\in K^n$ and $\ag'\subseteq\OK$ such that $\Nm(\ag')$ only depends on invariants of 
the field. To do this, we invert $\ag$ and write it as 
$$\ag^{-1} = \frac{1}{k}\bg,$$
where $k\in\Z_{>0}$ and $\bg\subseteq\OK$. As $\Nm(\ag)\in\ag$, we have $\Nm(\ag)\ag^{-1}\subseteq\OK$ and 
thus $k\leq \Nm(\ag)$. Therefore, 
$$\Nm(\bg) \leq \frac{\Nm(k)}{\Nm(\ag)}\leq \frac{k^{d}}{\Nm(\ag)} \leq \Nm(\ag)^{d-1}.$$
Then we use the LLL algorithm to find an element $\alpha\in\bg$ such that
$$\sqrt{T_2(\alpha)} \leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\bg)^{1/d}.$$
%\begin{align*}
%\sqrt{T_2(\alpha)} &\leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\bg)^{1/d} \\
%&\leq \sqrt{d}2^{d^2/2}|\Delta_K|^{1/2d}\Nm(\ag).
%\end{align*}
Our reduced ideal is 
$$\ag' := \left(\frac{\alpha}{k}\right)\ag \subseteq \ag^{-1}\ag = \OK.$$
The integrality of $\ag'$ comes from the definition of $\bg^{-1}$ and the fact that $\alpha\in\bg$. From the 
arithmetic-geometric mean, we know that $\Nm(\alpha)\leq T_2(\alpha)^{d/2}/d^d$, therefore 
$$\Nm(\alpha)\leq 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\bg),$$
and the norm of the reduced ideal can be bounded by $\Nm(\ag')\leq 2^{d^3/2}\sqrt{|\Delta_K|}$. On the other 
hand, we set $A' := (k/\alpha)A$, which induces a growth of the coefficients $a_i$ of $A$. Indeed, each 
$a_i$ is multiplied by $(k/\alpha)$. 

\begin{proposition}
The size of the normalized module is polynomialy bounded by $d$, $\log|\Delta_K|$ and the size of the input 
$S(A) + S(\ag)$.
\end{proposition}


\begin{proof}
Let $y,z\in\OK$, then 
\begin{align*}
S(yz) &\leq d \log\left( 2^{3d/2}\sqrt{T_2(yz)}\right)\\
&\leq d \log\left( 2^{3d/2}\sqrt{T_2(y)T_2(z)} \right) \\
&\leq d \left( \frac{3d}{2} + \log\left(\sqrt{T_2(y)}\right) + \log\left(\sqrt{T_2(z)}\right) \right)\\
&\leq d \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right) \left( \frac{3d}{2} + S(y) + S(z) \right)
\end{align*}
So we certainly have 
$$\forall y,z\in K,\  S(yz)\leq \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right) \left( \frac{3d}{2} + S(y) + S(z) \right),$$
Wich allows us to state 
$$S\left(a_i\frac{k}{\alpha}\right) \leq  \log\left(\sqrt{d}2^{d^2/2}\sqrt{|\Delta_K|}\right)\left(S(a_i) + n\log(k) + S\left(\frac{1}{\alpha}\right)\right).$$
In addition, if $\frac{1}{\alpha} = \frac{x}{k'}$ where $x\in\OK$ and $k'\in\Z_{>0}$, then 
$$S\left(\frac{1}{\alpha}\right)\leq \log(k') + d\log\left(2^{3d/2}\sqrt{T_2(x)}\right).$$
On the one hand, we have 
\begin{align*}
k' &\leq \Nm(\alpha)\\
&\leq 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1},
\end{align*}
and on the other hand, we need to bound $T_2(x)$. We notice that since $\Nm(\alpha)\in\Q$, 
$\forall j\leq d$, $\Nm(\alpha) = \alpha\beta = \sigma_j(\alpha\beta)$. We also know that 
$\forall j$, $\sqrt{T_2(\alpha)}\leq |\sigma_j(\alpha)|$. Therefore, 
$$\forall j\leq d, \ |\sigma_j(x)| = \frac{\Nm(\alpha)}{|\sigma_j(\alpha)|} 
 = \prod_{i\neq j}|\sigma_i(\alpha)|\leq T_2(\alpha)^{(d-1)/2}.$$
This allows us to bound $T_2(x)\leq \sqrt{d}T_2(\alpha)^{d-1}$, and thus
\begin{align*}
S\left( \frac{1}{\alpha}\right) &= \log(k') + S(x) \\
&\leq \log\left(\Nm(\alpha)\right) + \log\left( 2^{3d/2} \sqrt{T_2(x)}\right)\\
&\leq \log\left( 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) + \log\left( \sqrt{d}2^{3d/2}T_2(\alpha)^{d-1}\right)\\
&\leq \log\left( 2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) +
\log\left(d2^{(d^2+3d)/2}|\Delta_K|^{1/2d}\Nm(\ag)\right)\\
&= \log(d) + \frac{(d^3 + d^2 + 3d)}{2} + \frac{d+1}{2d}\log|\Delta_K| + d\log\Nm(\ag).
\end{align*}
%and on the other hand since $T_2(x)$ is the first minima of $(x)\subseteq\OK$ with respect to $T_2$, we 
%have from Minkowski's first theorem that 
%\begin{align*}
%\sqrt{T_2(x)}&\leq \sqrt{d}\left(\Nm(x)\sqrt{|\Delta|}\right)^{1/d}\\
%&\leq \sqrt{d}\left(\frac{k'^d}{\Nm(\alpha)}\sqrt{|\Delta|}\right)^{1/d}\\
%&\leq \sqrt{d}\left(k'^d\sqrt{|\Delta|}\right)^{1/d}.
%\end{align*}
%Therefore
%$$S\left(\frac{1}{\alpha}\right) \leq \log\left(2^{d^3/2}\sqrt{|\Delta_K|}\Nm(\ag)^{d-1}\right) + 
%d\log\left(2^{3d/2} \sqrt{d} k'|\Delta|^{1/2d}\right),$$
Therefore, the size $S\left(a_i\frac{k}{\alpha}\right)$ of the normalized vectors of our pseudo-basis is thus polyniomaly bounded by 
$d$, $n$, $\log|\Delta_K|$, $S(a_i)$, and $S(\ag)$. 
\end{proof}

Our normalization, summarized in Algorithm~\ref{alg:normalization}, was performed at the price of a 
reasonable growth in the size of the object we manipulate.
\begin{algorithm}[ht]
\caption{Normalization of a one-dimensional module}
\begin{algorithmic}[1]\label{alg:normalization}
\REQUIRE $A \in K^{n}$, fractional ideal $\ag$ of $K$.
\ENSURE  $A' \in K^{n}$, $\ag'\subseteq \OK$ such that $\Nm(\ag')\leq 2^{d^3/2}\sqrt{|\Delta_K|}$ and 
$\ag A = \ag' A'$.
\STATE $\ag \leftarrow k_0\ag$, $A \leftarrow A/k_0$ where $k_0$ is the denominator of $\ag$.
\STATE $\bg \leftarrow k \ag^{-1}$ where $k$ is the denominator of $\ag^{-1}$.
\STATE Let $\alpha$ be the first element of an LLL-reduced basis of $\bg$.
\STATE $\ag'\leftarrow \left(\frac{\alpha}{k}\right) \ag$, $A' \leftarrow \left(\frac{k}{\alpha}\right)A$.
\RETURN $\ag'$, $A'$.
\end{algorithmic}
\end{algorithm}

\section{Reduction of an element modulo a fractional ideal}

To achieve a polynomial complexity for our pseudo-HNF algorithm, we reduce some elements of $K$ modulo 
ideals whose norm can be reasonably bounded. We show in this section how to bound the norm of a reduced 
element with respect to the norm of the ideal and invariants of $K$. Let $\ag$ be a fractional ideal of 
$K$, and $x\in K$. Our goal is to find $\overline{x} \in K$ such that 
$\| \overline{x} \| := \sqrt{T_2(\overline{x})}$ 
is bounded, and that $x - \overline{x} \in \ag$. 

The reduction algorithm consists of finding an LLL-reduced basis $r_1,\cdots , r_d$ of $\ag$ and to decompose 
$$x = \sum_{i\leq d } x_i r_i.$$
Then, we define 
$$\overline{x} := x - \sum_{i\leq d } \lfloor x_i \rceil r_i.$$
Note that two different LLL-reduced basis for $\ag$ will lead to two different $\overline{x}$. One way around this 
is to apply the LLL algorithm to an HNF basis of $\ag$, which is unique. In the following, we do not assume uniqueness 
since it is not part of our results. 

\begin{proposition}
Let $x\in K$ and $\ag$ be a fractional ideal of $K$, then Algorithm~\ref{alg:reduction} returns $\overline{x}$ such that 
$x - \overline{x}\in\ag$ and 
$$\|\overline{x}\| \leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}.$$
\end{proposition}

\begin{proof}
Let $I$ be an integral ideal of $\OK$, and $\lambda_1,\cdots,\lambda_d$ its first $d$ successive minimas. From 
Minkowski's second theorem, we know that 
$$\prod_{j\leq d} \lambda_j \leq d^{d/2} \Nm(I)\sqrt{\Delta_K}.$$
In the meantime, the arithmetic-geometric mean applied to any $x\in I$ such that $\|x\| = \lambda_1$ implies that 
$$1\leq \Nm(I)^{2/d} \leq \Nm(x)^{2/d} \leq \frac{\|x\|^2}{d}, $$
and thus $\lambda_1 \geq \sqrt{d}\Nm(I)^{1/d}$. So in particular, every $\lambda_i$ has to satisfy 
$$\lambda_i\leq \sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$
The LLL~\cite{LLL} algorithm allows us to compute a basis $(r_j)_{j\leq d}$ for $I$ that satisfies
$$\|r_j\|\leq 2^{d/2}\lambda_i\leq 2^{d/2}\sqrt{d}\Nm(I)^{1/d}\sqrt{\Delta_K}.$$ 
The same holds for a fractional ideal $\ag$ of $K$. Indeed, by definition, there is a $k\in \Z$ such 
that $I = k\ag$ is an ideal of $\OK$, and if $(r_j)_{j\leq d}$ is an LLL-reduced basis for $\ag$, 
then $(kr_j)_{j\leq d}$ is an LLL-reduced basis for $I$ and we have 
\begin{align*}
 k\|r_j\| = \|kr_j \| &\leq  2^{d/2}\sqrt{d}\Nm(k\ag)^{1/d}\sqrt{\Delta_K} \\
&\leq  2^{d/2}\sqrt{d}\Nm((k))^{1/d} \Nm(\ag)^{1/d}\sqrt{\Delta_K} \\
&\leq  k\cdot 2^{d/2}\sqrt{d} \Nm(\ag)^{1/d}\sqrt{\Delta_K}.
\end{align*}
Then, as $\lfloor x_j \rceil r_j\leq 1$, we see that 
$$\|\overline{x}\|\leq d\max_j\|r_j\|\leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}.$$
\end{proof}

\begin{algorithm}[ht]
\caption{Reduction modulo a fractional ideal}
\begin{algorithmic}[1]\label{alg:reduction}
\REQUIRE $x\in K$, fractional ideal $\ag$ of $K$.
\ENSURE  $\overline{x}\in K$ such that $x - \overline{x} \in \ag$ and $\|\overline{x}\| \leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}$.
\IF{$\|x\| \leq d^{3/2}2^{d/2}\Nm(\ag)^{1/d}\sqrt{\Delta_K}$ \textbf{or} $x = 1$}
\RETURN $x$.
\ELSE
\STATE Compute an LLL-reduced basis $(r_i)_{i\leq d}$ of $\ag$.
\STATE Decompose $x = \sum_{i\leq d} x_i r_i$.
\STATE $\overline{x} \leftarrow x - \sum_{i\leq d } \lfloor x_i \rceil r_i.$
\RETURN $\overline{x}$.
\ENDIF
\end{algorithmic}
\end{algorithm}


\section{HNF Algorithm}

Let us assume that our module is integral, that is $M \subseteq \OK^n$. 
We use a variant of the modular version of~\cite[Alg. 1.4.7]{cohen2} that ensures that the current 
pseudo-basis $[\ag_i,A_i]_{i\leq n}$ of the module satisfies $\ag\subseteq\OK$ at every step of the 
algorithm. Algorithm~\ref{alg:HNF} computes the pseudo-HNF modulo the determinantal ideal $\g$, and 
Algorithm~\ref{alg:Euclidian} recovers an actual HNF for $M$. In this section, we discuss the differences 
between Algorithms~\ref{alg:HNF} and~\ref{alg:Euclidian} and their equivalent in~\cite[1.4]{cohen2}. We 
also prove the validity of Algorithm~\ref{alg:Euclidian} for the sake of completeness, although it is 
already said to be similiar to the integer case in~\cite[1.4]{cohen2}.   

%In addition, we use Algorithm~\ref{alg:normalization} to ensure that we know an absolute 
%bound on $\Nm(\ag_i)$ at every step. This, combined with reduction steps modulo the determinantal ideal
%$\g$, ensures that both the numerator and the denominator of our entries remain bounded throughout the 
%algorithm. 
After the original normalization, all the ideals are intefral. As we assume that our module is integral, we 
immediatly deduce that the ideal $\dg$ created at Step~6 
of Algorithm~\ref{alg:HNF} is integral as well. In addition, from the definition of the inverse of an ideal 
we also have that 
$$\frac{b_{i,i}\bg_ib_{i,j}\bg_j}{b_{i,j}\bg_j + b_{i,i}\bg_i}\subseteq \OK,$$
which allows us to conclude that the update of $(\bg_i,\bg_j)$ performed at Step~9 of Algorithm~\ref{alg:HNF}
preserves the fact that our ideals are integral. 

The computation of $u\in \bg_i\dg^{-1}$ and $v\in \bg_j\dg^{-1}$ such that $b_{i,j}u+ b_{i,i}v = 1$ at 
Step~7 is achieved by using~\cite[Th. 1.3.3]{cohen2} to obtain $x\in b_{i,j}\bg_i/\dg\subseteq\OK$, and 
 $y\in b_{j,j}\bg_j/\dg \subseteq\OK$, such that $x + y = 1$. We then set 
\begin{align*}
u &\leftarrow x/b_{i,j} \\
v &\leftarrow x/b_{j,j}
\end{align*}

\begin{algorithm}[ht]
\caption{HNF of a full-rank square pseudo-matrix modulo $\g$}
\begin{algorithmic}[1]\label{alg:HNF}
\REQUIRE $A \in K^{n\times n}$, $\ag_1,\cdots,\ag_n$ , $\g$.
\ENSURE pseudo-HNF $B$, $\bg_1,\cdots,\bg_n$ modulo $\g$. 
\STATE $B\leftarrow A$, $\bg_i\leftarrow \ag_i$, $j\leftarrow n$.
\STATE Normalize $[(B_i),(\bg_i)]_{i\leq n}$ with Algorithm~\ref{alg:normalization}
\WHILE { $j\geq 1$ }
\STATE $i \leftarrow j-1$.
\WHILE { $i\geq 1$ } 
\STATE $\dg \leftarrow b_{i,j}\bg_i + b_{j,j}\bg_j$
\STATE Find $u\in \bg_i\dg^{-1}$ and $v\in \bg_j\dg^{-1}$ such that $b_{i,j}u+ b_{j,j}v = 1$ 
with~\cite[Th. 1.3.3]{cohen2}.
\STATE $(B_i,B_j)\leftarrow (b_{j,j}B_i-b_{i,j}B_j,uB_i + vB_j)$.
\STATE $(\bg_i,\bg_j)\leftarrow (b_{i,j}\bg_ib_{j,j}\bg_j\dg^{-1},\dg)$.
\STATE Normalize $\bg_i,B_i$ with Algorithm~\ref{alg:normalization}.
\STATE Reduce $B_i$ modulo $\g\bg_i^{-1}$ and $B_j$ modulo $\g\bg_j^{-1}$ with Algorithm~\ref{alg:reduction}. 
\STATE $i\leftarrow i-1$.
\ENDWHILE
%\STATE $i\leftarrow j+1$.
%\WHILE {$i\leq n$}
%\STATE Find $q\in \bg_i\bg^{-1}_j$ such that $b_{i,j} - q$ is small.
%\STATE $B_i\leftarrow B_i-qB_j$, $i\leftarrow i+1$.
%\ENDWHILE
\STATE $j\leftarrow j-1$.
\ENDWHILE
\RETURN $(\bg_i)_{i\leq n}$, $B$.
\end{algorithmic}
\end{algorithm}

The normalization and reduction at Steps 10-11 allows us to keep the size of the $B_i$ and of the $\bg_i$ 
reasonably bounded by invariants of $K$ and the dimension of the module. By doing so, we give away some 
information about the module $M$. Indeed, at the end of Algorithm~\ref{alg:HNF}, we obtain a pseudo-basis 
$[(B_i)_{i\leq n},(\bg_i)_{i\leq n}]$ such that 
%$$\sum_{i\leq n} \bg_iB_i \subseteq M + \sum_{i\leq n}\g e_i,$$
$$\forall i\leq n\  \bg_iB_i \subseteq M + \g e_i,$$
where $e_i := (0,0,\cdots,1,0,\cdots,0)$ is the $i$-th vector of the canonical basis of $K^n$. 
Let $M_i\subseteq \OK^{n-i}$ be the $\OK$-module defined by 
$$\ag_1(a_{1,n-i},\cdots , a_{1,n}) + \cdots + \ag_n(a_{n,n-i},\cdots,a_{n,n}),$$
and $\g(M_i)$ its determinantal ideal. The operations performed at Step 6 to 10 in Algorithm~\ref{alg:HNF} preserve 
$\g(M_i)$ while after Step~11, our pseudo-basis $[(B_i)_{i\leq n},(\bg_i)_{i\leq n}]$ only defines a module $M'\subseteq\OK^n$
satisfying 
$$\g(M'_i) + \g = \g(M_i) + \g.$$
This property is the equivalent of the integer case when the HNF is taken modulo a multiple $D$ of the determinant of the 
lattice. To recover the ideals $\cg_i$ of a pseudo-HNF of $M$, we first notice that 
\begin{align*}
\forall i,\g(M_i) + \g &= \cg_{n-i}\cdots\cg_n + \g \\
&= \cg_{n-i}\cdots\cg_n + \cg_1\cdots \cg_n \\
&= \cg_{n-i}\cdots\cg_n.
\end{align*}
On the other hand, $\g(M'_i) + \g = \bg_{n-i}\cdots\bg_n + \g$. Thus, we have 
$$\forall i,\ \bg_{n-i}\cdots\bg_n +\g= \cg_{n-i}\cdots\cg_n,$$
which allows us to recursively recover the $\cg_i$ from the $(\bg_j)_{j\geq i}$ and $\g$. Indeed, as in the integer case, 
it boils down to taking 
$$\cg_i = \frac{\g}{\prod_{j > i}\cg_j} + \bg_i.$$
To do so, we keep track of $\g_i := \frac{\g}{\prod_{j > i}\cg_j}$ throughout Algorithm~\ref{alg:Euclidian}
that reconstructs the actual pseudo-HNF from its modular version. At each step we set 
$$\cg_i\leftarrow \bg_i + \g_{i}.$$
This replacement of the ideals in the pseudo-basis defining our module impacts the corresponding vectors 
in $K^n$ as well. In particular, we require that the diagonal elements all be 1. Do ensure thus, we find $u\in \bg_i\cg^{-1}_i,\ v\in \g_{i}\cg^{-1}_i$ such that $u + v = 1$ wich implies that 
$$\cg_i(uB_i + ve_i)\subseteq \bg_iB_i + \g_ie_i,$$
where the $i$-th coefficient of $uB_i + ve_i\in K^n$ is 1 and the coefficient of index $j>i$ in $uB_i + ve_i$
are 0. Then we set 
$$W_i\leftarrow uB_i\bmod \g_i\cg^{-1}_i,$$
and observe that $uB_i + ve_i = W_i + d_i$ where the coefficients of $d_i\in\left(\g_i/\cg_i\right)^n$ of 
index $j > i$ are 0. The vector $d_i$ satisfies $\cg_id_i\subseteq \g_id'_i$ where $d'_i\in\OK^n$ with coefficients $j>i$ equal to 0. This allows us to state that 
$$\cg_i W_i \subseteq \bg_iB_i + \g_ie_i  + \cg_id_i \subseteq M + \g_ie_i  + \g_id'_i \subseteq M + \g_iD_i,$$
where the coefficients of $D_i\in\OK^n$ of index $j>i$ equal 0. We now want to prove that 
$\cg_iW_i\subseteq M$. To do this, we prove that $\g_iD_i\subseteq M$. 

\begin{lemma}\label{lem:1}
Let $M = \ag_1A_1 + \cdots \ag_nA_n\in\OK^n$, then we have 
$$\g(M)\OK^n \subseteq M$$ 
\end{lemma}

\begin{proof}
We can prove by induction that if $[(B_i),(\bg_i)]$ is a pseudo-HNF basis of $M$, then 
$$\forall i,\ \g_1\cdots\g_i e_i \subseteq M,$$
where $e_i$ is the $i$-th vector of the canonical basis of $\OK^n$. Our statement immediatly follows.
\end{proof}

We now consider the intersection $N_i$ of our module $M\subseteq \OK^n$ with $\OK^i$. Note that with the 
previous definitions, we have in particular $M = N_i \oplus M_i$. 

\begin{lemma}
Let $i\leq n$ and $D\in\OK^n$ a vector whose entries of index $j>i$ are 0. Then we have 
$$\g_i D \subseteq M.$$
\end{lemma}

\begin{proof}
From Lemma~\ref{lem:1}, we know that $\g_i\OK^i \subseteq N_i$. If $D_i\in\OK^i$ is the first $i$ 
coordinates of $D$, then $\g_i D_i\subseteq N_i$, and as the last $n-i$ coordinates of $D$ are 0, we have 
$$\g_i D \subseteq M.$$
\end{proof}
The module generated by the pseudo-basis $[(W_i),(\cg_i)]$ computed by Algorithm~\ref{alg:Euclidian} is 
a subset of $M$. We ensured that its determinantal ideal $\prod_i\cg_i$ equals the determinantal ideal 
$\g$ of $M$. Let us prove that it is sufficient to ensure that 
$$\cg_1 W_1 + \cdots + \cg_n W_n = M.$$

\begin{lemma}\label{lem:3}
Let $M = \sum_{i\leq n} \ag_i A_i$ and $M' = \sum_{i\leq n} \bg_i B_i$ two $n$-dimensional $\OK$-modules 
such that $M'\subseteq M$ and $\g(M') = \g(M)$. Then necessarily 
$$M = M'.$$
\end{lemma}

\begin{proof}
Let $[(W_i),(\cg_i)]$ be a pseudo-HNF for $M$, and $[(W'_i),(\cg'_i)]$ a pseudo-HNF for $M'$. By assumption, we have $\prod_i\cg_i= \prod_i\cg'_i$, and $M'\subseteq M$. As both matrices $W$ and $W'$ have a lower
triangular shape, it is clear that 
\begin{equation}
 \forall i, \ \sum_{j\leq i}\cg'_jW'_j \subseteq \sum_{j\leq i} \cg_jW_j.\label{eq:mod_inc}
\end{equation}
As the diagonal coefficients of both $W$ and $W'$ are 1, we see by looking at the inclusion in the coefficient $i$ of~\eqref{eq:mod_inc} that $\cg'_i\subseteq \cg_i$. Then as $\g(M) = \g(M')$, we have 
$$\forall i \cg_i = \cg'_i.$$
Now let us prove by induction that 
\begin{equation}
 \forall i,\ \cg_iW_i \subseteq \cg_1W'_1 + \cdots + \cg_iW'_i.\label{eq:rec_mod_inc}
\end{equation}
This assertion is clear for $i=1$ since $W_1 = W'_1 = e_1$. Then, assuming~\eqref{eq:rec_mod_inc} for 
$1,\cdots,i-1$, we first use the fact that 
$$\cg_iW'_i \subseteq \cg_1W_1 + \cdots + \cg_i W_i.$$
In other words, $\forall c'_i\in\cg_i$, $\exists (c_1,\cdots,c_i)\in\cg_1\times\cdots\times\cg_i$ such that 
$$c'_i(w'_{i,1},\cdots,w'_{i,i-1},1) = \left(\sum_{1\leq j\leq i} c_jw_{j,1} , \cdots , c_{i}w_{i,i-1} + c_{i-1} , c_i\right).$$ 
In particular, $c_i = c'_i$, which allows us to state that $\forall c_i\in\cg_i$, 
$\exists (c_1,\cdots,c_{i-1})\in\cg_1\times\cdots\times\cg_{i-1}$ such that 
\begin{align*}
c_i w_{i,i-1} &= c_{i-1}  + c_i w'_{i,i-1} \\
c_i w_{i,i-2} &= c_{i-2}  + c_{i-1} w_{i-1,i-2} + c_iw'_{i,i-2} \\
\vdots\ \  &=\ \  \vdots \\
c_i w_{i,1} &= c_{1} + \cdots + c_{i-1} w_{i-1,1} + c_iw'_{i,1}.
\end{align*}
This shows that 
$$\cg_iW_i \subseteq \cg_1W_1 + \cdots + \cg_{i-1}W_{i-1} + \cg_iW'_i,$$
and since we have $\forall j<i,\ \cg_jW_i\subseteq \sum_{j<i}\cg_jW'_j$, we obtain the desired result.
\end{proof}

Lemma~\ref{lem:3} is a generalization of the standard result on $\Z$-modules stating that if $L'\subseteq L$
and $\det(L) = \det(L')$, then $L = L'$. Although implied in~\cite[Chap. 1]{cohen2}, Lemma~\ref{lem:3} is 
not stated, nor proved in the litterature. Yet, it is essential to ensure the validity of 
Algorithm~\ref{alg:Euclidian}. 

\begin{proposition}
The $\OK$-module defined by the pseudo-basis $[(W_i),(\cg_i)]$ obtained by applying lgorithm~\ref{alg:Euclidian} to the pseudo-HNF of $M$ modulo $\g(M)$ satisfies 
$$\cg_1 W_1 + \cdots + \cg_n W_n = M.$$
\end{proposition} 

\begin{algorithm}[ht]
\caption{Eucledian reconstruction of the pseudo-HNF}
\begin{algorithmic}[1]\label{alg:Euclidian}
\REQUIRE $B \in K^{n\times n}$, $\bg_1,\cdots,\bg_n$ output of the pseudo-HNF modulo $\g$ for 
$M\subseteq \OK^n$.
\ENSURE A pseudo HNF $W$,$\cg_1,\cdots,\cg_n$ for $M$. 
\STATE $j\leftarrow n$ , $\g_j\leftarrow \g$.
\WHILE { $j\geq 1$ }
\STATE $\cg_j\leftarrow \bg_j + \g_j$.
\STATE Find $u\in \bg_j\dg^{-1}$ and $v\in \g\cg^{-1}_j$ such that $u + v = 1$.
\STATE $W_j\leftarrow uB_j\bmod \g\cg^{-1}_j$.
\STATE $\g_j \leftarrow \g_j\cg^{-1}_j$.
%\STATE $i\leftarrow j+1$.
%\WHILE {$i\leq n$}
%\STATE Find $q\in \bg_i\bg^{-1}_j$ such that $w_{i,j} - q$ is small.
%\STATE $W_i\leftarrow W_i-qW_j$, $i\leftarrow i+1$.
%\ENDWHILE
%\STATE $\g\leftarrow \g\dg^{-1}$.
\STATE $j\leftarrow j-1$.
\ENDWHILE
\RETURN $W,(\cg_i)_{i\leq n}$.
\end{algorithmic}
\end{algorithm}

\section{Complexity of the HNF}\label{sec:complexity}

Let us assume that we are able to compute the determinantal ideal $\g$ of our module $M$ in polynomial time 
with respect to the bit size of the invariants of the field and of $S(\g)$. In this section, we show that 
Algorithm~\ref{alg:HNF} and Algorithm~\ref{alg:Euclidian} are polynomial wih respect to the same parameters.
This result is analogous to the case of integers matrices. Indeed, the only thing we need to verify is that 
the size of the elements remain remains reasonably bounded during the algorithm. The number of operations is 
the same as in the integer case (modulo a constant factor). 

In Algorithm~\ref{alg:HNF}, the coefficient explosion is prevented by the modular reduction of Step~11. It ensures that 
$$\forall i<j, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g\bg_i^{-1})^{1/d}\sqrt{|\Delta_K|}.$$
In addition, since $\bg_i$ is integral, we have 
$$\forall i<j, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g)^{1/d}\sqrt{|\Delta_K|}.$$
This is not enough to prevent the explosion since $b_{i,j}$ might not be integral. Therefore, there is a 
minimal $k\in\Z_{>0}$ such that $kb_{i,j}\in\OK$, which we need to bound to ensure that $S(b_{i,j})$ remains bounded as well. We know that $b_{i,j}\bg_i\subseteq\OK$, and that $\bg_i$ is integral. Thus, 
$\Nm(k)\mid \Nm(\bg_i)$, which in turns implies that $k\leq \Nm(\bg_i)$. As on the other hand, the 
normalization of Step~10 ensures that $\Nm(\bg_i)\leq 2^{d^2/2}\sqrt{|\Delta_K|}$, we conclude that 
\begin{align*}
k &\leq 2^{d^2/2}\sqrt{|\Delta_K|}\\
S(b_{i,j}) &\leq \log(k) + d\log\left(2^{3d/2}\|kb_{i,j}\|\right) \\ 
&\leq \log\left(2^{d^2/2}\sqrt{|\Delta_K|}\right) + d\log\left(d^{3/2}2^{2d+d^2/2}\Nm(\g)^{1/d}|\Delta_K|\right).
\end{align*}

In Algorithm~\ref{alg:HNF}, we last manipulate $B_j$ and $\bg_j$ when the index $j$ is the pivot. In that 
case, we cannot use the normalization to bound the size since we require that $b_{j,j} = 1$. Fortunately, for each $i$. we 
reduced $B_i$ modulo $\g\bg_i$, which means that 
$$\forall i, \ \|b_{i,j}\|\leq d^{3/2}2^{d/2}\Nm(\g\bg_i^{-1})^{1/d}\sqrt{|\Delta_K|}.$$
In addition, the arithmetic-geometric tells us that $\|b_{i,k}\|\geq \sqrt{d}\Nm(b_{i,k})^{1/d}$, which in turn implies that 
$$\forall i, \Nm(b_{i,j}\bg_i)\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}.$$
As we know that $\Nm(b_{i,j}\bg_i + b_{j,j}\bg_j) \leq \max(b_{i,j}\bg_i,b_{j,j}\bg_j)$, we therefore know that Step~9 ensures that 
$\Nm(\bg_j)\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}$, which allows us to bound the size of the denominators in the $j$-th row 
the same way we did for the indices $i<j$
\begin{align*}
k &\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\\
S(b_{i,j}) &\leq \log(k) + d\log\left(2^{3d/2}\|kb_{i,j}\|\right) \\ 
&\leq \log\left(d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\right) + \log\left(d^{d+3/2}2^{2d+d^2/2}\Nm(\g)^{1/d}|\Delta_K|^{(d+1)/2}\right).
\end{align*}

The Euclidian reconstruction of Algorithm~\ref{alg:Euclidian} can be seen as another pivot operation 
between the two one-dimensional $\OK$-modules $\bg_j B_j$ and $\g_je_j$. We can 
therefore bound the entries of $W$ by the same method as for Step~6-11 of Algorithm~\ref{alg:HNF}, we the 
extra observation 
$$\Nm(\g_j)\leq \Nm(\g).$$
Therefore, we showed that we could bound the size of the objects that are manipulated 
throughout the algorithm by values that are polynomial in terms of $n$, $d$, $S(\g)$ and $\log(|\Delta_K|)$. The complexity of 
the HNF algorithm is therefore polynomial in these values.

\section{Computing $\g$}

Let us assume that $A\in\OK^{n\times n}$. If it is not the case, then we need to multiply by the common 
denominator $k$ of the entries of $A$ and return $\det(kA)/k^n$. In this section, we describe how to compute $\g$ in polynomial time with respect to $n$, $d$, $\log|\Delta_K|$ and the size of the entries of $A$. The idea is to compute $\det(A)\mod (p)$ for a sufficiently large prime number $p$. In practice, one might 
prefer to compute $\det(A)\mod (p_i)$ for several prime numbers $p_1,\cdots,p_l$ and recombine the values 
via the chinese remainder theorem, but for the sake of simplicity, we only describe that procedure for a 
single prime. Once $\det(A)$ is computed in polynomial time, we return 
$$\g = \det(A)\cdot \ag_1\cdots \ag_n.$$

The first step consists of evaluating how large $p$ should be to ensure that we recover $\det(A)$ 
uniquely. We make the assumption that $p$ does not split totally in $K$, that is $\Nm((p))\leq p^{d-1}$. 
The LLL reduction modulo $(p)$ returns $\overline{\det(A)}$ such that 
$$\|\overline{\det(A)}\| \leq d^{3/2}2^{d/2}\Nm((p))^{1/d}\sqrt{|\Delta_K|}\leq p^{(d-1)/d}d^{3/2}2^{d/2}\sqrt{|\Delta_K|}.$$
Assume that a bound on $\|\det(A)\|$ is known, and that $p$ is large enough to ensure that 
$\|\det(A)\|\leq p^{(d-1)/d}d^{3/2}2^{d/2}\sqrt{|\Delta_K|}$ as well. Now we need to prove that 
$\det(A) = \overline{\det(A)}$. We know that there exists $k\in\Z$ such that 
$$\det(A) = \overline{\det(A)} + kp.$$ 
In addition, if $\overline{\|\det(A)\|} = \sum_i \overline{a_i}\omega_i$, then from~\cite[Lem. 2]{stehle_fieker_LLL}, 
we have  
$$\forall i,\ |\overline{a_i}| \leq 2^{3d/2}\|\overline{\det(A)}\|\leq 2^{2d}p^{(d-1)/d}d^{3/2}\sqrt{|\Delta_K|}.$$
Without loss of generality, we can assume that $\omega_1 = 1$. We now show that if $p$ is large enough, then 
the first coefficient of $\det(A)$ will be too large for the condition on $\|\det(A)\|$ to be satisfied, 
unless $k = 0$. We write $\det(A) = \sum_i a_i\omega_i$. In particular, $a_1 = \overline{a}_1 + kp$, and 
if $k\neq 0$ and $p$ is chosen large enough to satisfy 
$$\log(p) > d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right), $$
then we have $|a_1| > p/2$. As we know that $|a_1|\leq 2^{3d/2}\|\det(A)\|$, this gives us on the other 
hand 
$$\log(p) < \log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right),$$
which is impossible. We conclude that is $p$ is a non totally split prime in $K$ satisfying 
\begin{align*}
\log(p) &> d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right) \\
\log(p) &\geq \frac{d}{d-1}\left( \log\left(\|\det(A)\|\right) - \frac{3}{2}\log(d) - \frac{d}{2} \right),
\end{align*}
then $\overline{\det(A)} = \det(A)$. 

Now, let us see how to find a bound on $\|\det(A)\|$. We first compute an upper bound on $|\sigma(\det(A))|$ for the $d$ complex embeddings $\sigma$ of $K$ via Hadamard's inequality and then we deduce a bound on $\|\det(A)\|$. Let $\sigma : K\rightarrow\mathcal{C}$, we know from Hadamard's inequality that 
$$|\sigma(\det(A))|\leq B^n n^{n/2},$$
where $B$ is a bound on $\sigma(a_{i,j})$. Such a bound can be derived from the size of the coefficient 
of $A$ by using 
$$\forall x, \ \forall i\ |\sigma_i(x)| \leq \left(\max_j|x_j|\right)d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.$$
This way, we see that $B := 2^{\max_{i,j}S(a_{i,j})}d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}$ suffices. Then, our 
bound on $\|\det(A)\|$ is simply 
$$\|\det(A)\| \leq \sqrt{n} 2^{\max_{i,j}S(a_{i,j})}d^{3/2}2^{d^2/2}\sqrt{|\Delta_K|}.$$

\begin{algorithm}[ht]
\caption{Computation of $\det(A)$}
\begin{algorithmic}[1]\label{alg:det_ideal}
\REQUIRE $A\in \OK^{n\times n}$
\ENSURE $\det(A)$.
\STATE $B_1\leftarrow d\log\left(2^{2d+1}d^{3/2}\sqrt{|\Delta_K|}\right)$.
\STATE $B_2 \leftarrow \frac{d}{d-1}\left( \log(n)/2 +  \max_{i,j}(S(a_{i,j})) \right)$.
\STATE Let $p\in\N$ be the smallest non totally split prime above  $\max(B_1,B_2)$ and $(\p_i,e_i)_{i\leq g}$ such that $(p)=\prod_{i\leq g}\p_i^{e_i}$. 
\FOR {$\p_i\mid(p)$}
\STATE Compute $\det(A)\bmod \p_i$.
\ENDFOR
\STATE Recover $\det(A)\bmod (p)$ via 
\[   \left. \begin{array}{ccc}
    \OK/\p_1^{e_1}\times \cdots \times \OK/\p_g^{e_g}     & \longrightarrow  &   \OK/(p)\\
    (\det(A)\bmod \p_1^{e_1},\cdots ,\det(A) \bmod \p_g^{e_g})   & \longmapsto & \det(A)\bmod (p). \end{array} \right. \] 
\RETURN $\det(A)$.
\end{algorithmic}
\end{algorithm}

\section{Intersection of $\OK$-modules}

In this section, we prove that we can intersect $\OK$-modules in polynomial time with respect to the 
invariants of $K$ and of the sizes of the modules. The algorithm described in~\cite[Alg. 1.5.1]{cohen2} 
allows us to intersect two modules of $\OK^{n\times n}$ given by their pseudo-basis at the cost of the 
computation of the pseudo-HNF of a module in $\OK^{n\times n}$. 

 Let $M,N$ are two modules over a Dedekind domain given by $A,(\ag_i)_{i\leq l+1}$ and $B,(\bg_i)_{i\leq l+1}$, and let $C$ 
be the pseudo-matrix given by
\[ \left( \begin{array}{cc}
A & A  \\
0 & B  \end{array} \right),\]
and $\cg_1,\cdots,\cg_{2(l+1)}$. Then the upper left $(l+1)\times (l+1)$ minor for the HNF of $C$, together with $\cg_1,\cdots,\cg_n$ represent $M\cap N$ (see the proof of~\cite[Alg. 1.5.1]{cohen2}).

It is easy to see that $\g(C) = \g(A)\cdot\g(B)$. Therefore, the cost of Algorithm~\ref{alg:HNF} applied 
to $(C , (\cg_i)_{i\leq 2n})$ is polynomial in $n$, $d$, $\log|\Delta_K|$, $S(\g(M))$ and $S(\g(N))$. We showed that we could bound the output of Algorithm~\ref{alg:HNF} by a polynomial expression in the 
field invariants and $\g(C)$. Namely, the coefficients $\left(\frac{n_{i,j}}{d_{i,j}}\right)_{i,j\leq 2n}$ of the resulting matrix in $K^{2n\times 2n}$ satisfy 
\begin{align*}
|d_{i,j}|&\leq d^d 2^{d^2/2} \Nm(\g)^d |\Delta_K|^{d/2}\\
S(n_{i,j}) &\leq \log\left(d^d 2^{d^2/2} \Nm(\g(C))^d |\Delta_K|^{d/2}\right) + \log\left(d^{d+3/2}2^{2d+d^2/2}\Nm(\g(C))^{1/d}|\Delta_K|^{(d+1)/2}\right),
\end{align*}
while the ideals $\cg_i$ are integral of norm bounded by $\Nm(\g(C))$. Therefore, the cost of intersecting 
$k$ modules $M_1,\cdots,M_k$ is polynomial in $k$, $d$, $\log|\Delta_K|$, and the size of 
$$\g:= \g(M_1)\cdots\g(M_k),$$
since after each intersection of two modules the size of our output is bounded by absolutes bounds.


\begin{algorithm}[ht]
\caption{Intersection of $\OK$-modules}
\begin{algorithmic}[1]\label{alg:int_OK_mod}
\REQUIRE $\OK$-modules $M_1,\cdots,M_n$ given by $(A_1,(\ag^{(1)}_i)_{i\leq l+1}),\cdots,(A_n,(\ag^{(n)}_i)_{i\leq l+1})$.
\ENSURE A pseudo matrix $(H , (\cg_i)_{i\leq l+1})$ representing $\cap_i M_i$
\STATE $H\leftarrow A_n$, $(\cg_i)\leftarrow (\ag^{(n)}_i)$.
\FOR { $i\leq n-1$ }
\STATE Let $C,(\dg_i)_{i\leq 2(l+1)}$ 
be the pseudo-matrix given by
\[ \left( \begin{array}{cc}
H & H  \\
0 & A_i  \end{array} \right),\]
and $\cg_1,\cdots,\cg_{(l+1)},\ag^{(i)}_1,\cdots,\ag^{(i)}_{l+1}.$
\STATE Let $H$ be the upper left $l\times l$ minor of $C$ and $(\cg_i)_{i\leq l+1}\leftarrow (\dg_i)_{i\leq l+1}$.
\ENDFOR
\RETURN $(H , (\cg_i)_{i\leq l+1})$.
\end{algorithmic}
\end{algorithm}

\section{Application to coding theory}

Algorithms for list decoding Reed-Solomon codes, and their generalization the algebraic-geometric codes 
are now well understood. The codewords consist of sets of functions whose evaluation at a certain number of points 
are sent, thus allowing the receiver to retrieve them provided that the number of errors is manageable. Some algebraic-geometric 
codes beat the Gilbert-Varshamov bound for alphabet sizes $q > 49$ (see~\cite{garcia_stich,Zink}), and possess a nice algebraic structure which enables to decode even in the presence of a large number of errors~\cite{guruswami_sudan_reed_sol,wasserman}.

The idea behind behind algebraic-geometric codes can be adapted to define algebraic codes whose messages are encoded 
as a list of residues redundant enough to allow errors during the transmission. The Chinese Remainder codes (CRT codes) have been fairly studied by the community~\cite{guruswami_sudan_soft_CRT,Mandelbaum}. The encoded messages are residues modulo $N:=p_1,\cdots,p_n$ of numbers $m\leq K:= p_1\cdots p_k$ where $p_1 < p_2 < \cdots < p_n$ are prime numbers. They are encoded by using 
\[   \left. \begin{array}{ccc}
         \Z & \longrightarrow  & \Z/p_1\times \cdots \times \Z/p_n \\
        m & \longmapsto & (m\bmod p_1,\cdots ,m \bmod p_n). \end{array} \right. \] 
Decoding algorithms for CRT codes were significantly improved to reach the same level of tolerance to errors as those 
for Reed-Solomon codes~\cite{Boneh,sudan,guruswami_sudan_soft_CRT}. As algebraic-geometric codes are a generalization of Reed-Solomon codes, the idea arose that we could generalize the results for CRT codes to redundant residue codes based on number fields. Indeed, we can easily define an analogue of the CRT codes where a number field $K$ plays the role of $\Q$ and its ring of integers $\OK$ plays the role of $\Z$. Then, for prime ideals $\p_1,\cdots,\p_n$ such that $\Nm(\p_1) < \cdots < \Nm(\p_n)$, a message $m\in\OK$ can be encoded by using
\[   \left. \begin{array}{cccc}
      &   \OK & \longrightarrow  & \OK/\p_1\times \cdots \times \OK/\p_n \\
    c:&    m & \longmapsto & (m\bmod \p_1,\cdots ,m \bmod \p_n). \end{array} \right. \] 
The construction of good codes on number fields have been independantly studied by Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}. They provided indications on how to chose number fields having good properties for the underlying codes, but they did not describe any decoding algorithm.

\subsection{Johnson-type bound for number fields codes}

\input{johnson.tex}

\subsection{General description of the algorithm}

In this section, we give a high-level description of our decoding algorithm. We follow the approach of the general framework described in~\cite{guruswami_phd}, making the arrangements required in our context. Our code is the set of $m\in\OK$ such that $\|m\|\leq B$ where $B = \prod_{i\leq k}\Nm(\p_i)$. We also define $N:=\prod_{i\leq n}\Nm(\p_i)$. A codeword $m$ is encoded via 
\[   \left. \begin{array}{ccc}
         \OK & \longrightarrow  & \OK/\p_1\times \cdots \times \OK/\p_n \\
       m & \longmapsto & (m\bmod \p_1,\cdots ,m \bmod \p_n). \end{array} \right. \] 
Let $z_1,\cdots,z_n$ be non-negative real numbers, and let $Z$ be a parameter. In this section, as well as in Section~\ref{sec:existence} and~\ref{sec:computation}, we assume that the $z_i$ are integers. We assume that we received a vector $r_1,\cdots,r_n\in\prod_i\OK/\p_i$. We wish to retrieve all the codewords $m$ such that $\sum_i a_iz_i > Z$ where $a_i=1$ if $m\bmod \p_i = r_i$ and 0 otherwise (we say that $m$ and $(r_i)_{i\leq n}$ have weighted agreement $Z$).

We find the codewords $m$ with desired weighted agreement by computing roots of a polynomial $c\in\OK[y]$ that satisfies 
\begin{equation}\label{eq:cond_norm}
\|m\|\leq B \Longrightarrow \|c(m)\| < F,
\end{equation} 
for an appropriate bound $F$. A polynomial $c$ satisfying~\eqref{eq:cond_norm} is chosen in the ideal $\prod_{i\leq n}J_i^{z_i}\subseteq\OK[y]$ where
$$J_i = \{ a(y)(y-r_i) + p\cdot b(y)\mid a,b\in\OK[y]\ \text{and}\ p\in\p_i\}.$$
With such a choice of a polynomial, we necessarily have $c(m)\in\prod_i \p_i^{z_ia_i}$, where $a_i = 1$ if $c(m)\bmod \p_i = r_i$, $0$ otherwise. In particular, if $c(m)\neq 0$ this means that $\Nm(c(m)) \geq \prod_i\Nm(\p_i)^{z_ia_i}$. In addition, we know from the arithmetic-geometric inequality that $\|c(m)\| \geq \sqrt{d}\Nm(c(m))^{1/d}$. We thus know that if the weighted agreement satisfies 
\begin{equation}\label{eq:cond_weight}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) > -\frac{d}{2}\log(d) + d\log(F),
\end{equation}
which in turns implies $\sqrt{d}\left(\prod_i\Nm(\p_i)^{z_ia_i}\right)^{1/d} > F$, then $c(m)$ has to be zero, since otherwise it would contradict~\eqref{eq:cond_norm}.

\begin{algorithm}[H]
\caption{Decoding algorithm}
\begin{algorithmic}[1]\label{alg:decoding}
\REQUIRE $\OK$, $z_1,\cdots,z_n$, $B$, $Z$, $r_1,\cdots,r_n\in\prod_i\OK/\p_i$.
\ENSURE All $m$ such that $\sum_i a_iz_i > Z$.
\STATE Compute $l$ and $F$.
\STATE Find $c\in\prod_{i\leq n}J_i^{z_i}\subseteq\OK[y]$ of degree at most $l$ such that $\|m\|\leq B \Longrightarrow \|c(m)\| < F$.
\STATE Find all roots of $c$ and report those roots $\xi$ such that $\|\xi\|\leq B$ and $\sum_i a_iz_i > Z$.
\end{algorithmic}
\end{algorithm}

\subsection{Existence of the decoding polynomial}\label{sec:existence}

In this section, we prove the existence of a polynomial $c\in\OK[y]$ and a constant $F>0$ such that for all $\|m\|\leq B$, $m\in\OK$, we have $\|c(m)\|\leq F$. This proof is not constructive. The actual computation of this polynomial will be described in Section~\ref{sec:computation}. We first need to estimate the number of elements of $\OK$ bounded by a given size. 

\begin{lemma}\label{lem:Minkowski}
Let $F'>0$ and $0<\gamma < 1$, then the number of $x\in\OK$ such that $\|x\|\leq F'$ is at least
$$\left\lfloor \frac{\pi^{d/2}F'^d}{2^{r_1+r_2-1+\gamma}\sqrt{|\Delta|}\Gamma(d/2)}\right\rfloor.$$
\end{lemma}

\begin{proof}
As in~\cite[Chap. 5]{neukirch}, we use the standard results of Minkowski theory for our purposes. More precisely, there is an isomorphism
$$f:K_\R\longrightarrow \R^{r_1 + 2r_2}$$
and a scalar product $(x,y) := \sum_{i\leq r_1}x_iy_i + \sum_{r_1<i\leq r_2}2x_iy_i$ on $\R^{r_1+2r_2}$ transfering the canonical measure from $K_\R$ to $\R^{r_1+2r_2}$. Let $\lambda = f(\OK)$, $X := \{ x\in K_\R\mid \|x\|\leq F'\}$, and $m\in\N$. We know from Minkowski's lattice point theorem that if
$$\operatorname{Vol}(X) > m2^d\det(\lambda),$$
then $\#(f(x)\cap\lambda) \geq m$. As $\operatorname{Vol}(X) = 2^{r_2}\left(2\pi^{d/2}F'^d/\Gamma(d/2)\right)$ and $\det(\lambda) = \sqrt{|\Delta|}$, we have the desired result.
\end{proof}

Then, we must derive from Lemma~\ref{lem:Minkowski} an analogue of~\cite[Lemma 7.6]{guruswami_phd} in our context. This lemma allows us to estimate the number of polynomials of degree $l$ satisfying~\eqref{eq:cond_norm}. To simplify the expressions, we use the following notation in the rest of the paper
$$\add := \frac{\pi^{d/2}}{2^{r_1 + r2-1 + \gamma}\sqrt{|\Delta|}\Gamma(d/2)}.$$

\begin{lemma}\label{lem:nb_pol}
For positive integers $B,F'$, the number of polynomial $c\in\OK[y]$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} is at least
$$\left( \add \left( \frac{F'}{(l+1)B^{l/2}}\right)^d\right)^{l+1}.$$ 
\end{lemma}

\begin{proof}
Let $c(y) = c_0 + c_1y + \cdots + c_ly^l$. We want the $c_i$'s to satisfy $\|c_im^i\|< F'/(l+1)$ whenever $\|m\|\leq B$. This is the case when $\|c_i\| < F'/(B^i(l+1))$. By Lemma~\ref{lem:Minkowski}, there are at least $\add\left(F'/((l+1)B^i)\right)^d$ possibilities for $c_i$. Therefore, the number of polynomial $c$ satisfying~\eqref{eq:cond_norm} is at least 
$$(\add)^{l+1}\left(\left(\frac{F'}{l+1}\right)^{l+1}\prod^l_{i = 0}B^{-i}\right)^d,$$
which finishes the proof. 
\end{proof}

Now that we know how to estimate the number of $c\in\OK[y]$ or degree at most $l$ satisfying~\eqref{eq:cond_norm}, we need to find a lower bound on $F$ to ensure that we can find such a polynomial in $\prod_iJ_i^{z_i}$. The following lemma is an equivalent of~\cite[Lemma 7.7]{guruswami_phd}.

\begin{lemma}
Let $l,B,F$ be positive integers, there exists $c\in\prod_i J_i^{z_i}$ satisfying~\eqref{eq:cond_norm} provided that
\begin{equation}\label{eq:cond_F}
F > 2(l+1)B^{l/2}\frac{1}{(\add)^{1/d}}\left(\prod_i\Nm(\p_i)^{\binom{z_i+1}{2}}\right)^{\frac{1}{d(l+1)}}.
\end{equation}
\end{lemma} 

\begin{proof}
Let us apply Lemma~\ref{lem:nb_pol} to $F' = F/2$. There are at least 
$$\left( \add \left( \frac{F/2}{(l+1)B^{l/2}}\right)^d\right)^{l+1}$$
polynomial $c\in\OK[y]$ satisfying $\|m\|\leq B\Rightarrow \|c(m)\| < F/2$. In addition, we know from~\cite[Corollary 7.5]{guruswami_phd} that $\prod_i\left|\Nm(\p_i)\right|^{\binom{z_i+1}{2}}\geq \left|\OK[y]/\prod_i J_i^{z_i}\right|$, which implies that if~\eqref{eq:cond_F} is satisfied, then necessarily
$$\left( \add \left( \frac{F/2}{(l+1)B^{l/2}}\right)^d\right)^{l+1} > \left|\OK[y]/\prod_i J_i^{z_i}\right|.$$
This means that there are at least two distinct polynomials $c_1,c_2\in\OK[y]$ of degree at most $l$ such that $(c_1-c_2)\in\prod_i J_i^{z_i}$ and $\|c_1(m)\|,\|c_2(m)\| < F/2$ whenever $\|m\|\leq B$. The choice of $c:=c_1-c_2$ finishes the proof.
\end{proof}


\subsection{Computation of the decoding polynomial}\label{sec:computation}

Let $l>0$ be an integer to be determined later. To compute $c\in\prod_i J_i^{z_i}$ of degree at most $l$ 
satisfying~\eqref{eq:cond_norm}, we need to find a short pseudo-basis of the sub $\OK$-module $M$ of $K^{l+1}$ given by
$$c = c_0 + yc_1 + \cdots + y^lc_l \longrightarrow (c_0 , c_1 , \cdots , c_l).$$
We first compute a peudo-generating set for each $J_i^{z_i}$, then we compute a pseudo-basis for their intersection, and we 
finally call the algorithm of~\cite{stehle_fieker_LLL} to produce a short peudo-basis of $M$ from which we derive $c$. 



\begin{algorithm}[ht]
\caption{Computation of the decoding polynomial}
\begin{algorithmic}[1]\label{alg:comp_c}
\REQUIRE $(\p_i,z_i)_{i\leq n}$, $l$, $N$, $B$, $F$ such that $\exists c\in \prod_iJ_i^{z_i}$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} for $F$, and the encoded message $(r_1,\cdots,r_n)\in\prod_i\OK/\p_i$. 
\ENSURE $c\in \prod_iJ_i^{z_i}$ satisfying~\eqref{eq:cond_norm} for $F' = 2^{\frac{dl}{2}}\sqrt{l+1}\left(2^{2 + d\left(6 + 3d\right)} d^3|\Delta|^{2 + \frac{11}{2d}}\right) F$ of degree at most $l$.
%\STATE $L\leftarrow 2^{ld^2/2}\binom{2l}{l}N^l|\Delta|^{l/2}$.
\FOR {$i\leq n$}
\STATE $\tilde{z_i}\leftarrow \min(z_i,l)$.
\STATE For $0\leq j\leq \tilde{z_i}$: $\ag^i_j\leftarrow \p_i^{z_i-j}$, $a^i_j\leftarrow (y-r_i)^j$.
\STATE For $1\leq j\leq l-z_i$: $\ag^i_j\leftarrow \OK$,  $a^i_j\leftarrow y^j(y-r_i)^{z_i}$.
\STATE Let $\left(A_i,(\ag^i_j)_{j\leq l+1}\right)$ be the pseudo matrix representing $J_i^{z_i}$.
\STATE Compute $\g(J_i^{z_i})$ with Algorithm~\ref{alg:det_ideal}.
\ENDFOR
\STATE Compute a pseudo-basis $[(c_i),(\cg_i)]_{i\leq l+1}$ of $M=\cap_i J_i^{z_i}$ modulo $\g = \prod_i\g(J_i^{z_i})$ with algorithm~\ref{alg:int_OK_mod}.
\STATE Deduce a pseudo basis $[(d_i),(\dg_i)]_{i\leq l+1}$ of the module $M'$ given by
$$(v_0, v_1,\cdots,v_l)\in M\Longleftrightarrow (v_0, v_1\cdot B,\cdots,v_l\cdot(B)^l)\in M'.$$
\STATE Let $[(b_i),(\bg_i)]_{i\leq l+1}$ be a short peudo-basis of $M'$ obtained with the reduction algorithm of~\cite{stehle_fieker_LLL}.
\STATE Let $x_1,x_2$ be a short basis of $\bg_1$ obtained with~\cite[Th. 3]{stehle_fieker_LLL}.
\RETURN $c\in M$ corresponding to $x_1b_1\in M'$.
\end{algorithmic}
\end{algorithm}

\begin{proposition}
Algorithm~\ref{alg:comp_c} is correct and runs in polynomial time in $\log(N)$, $l$, $d$, and $\log|\Delta|$.
\end{proposition}

\begin{proof}
The loop between Step 1 and Step 8 of Algorithm~\ref{alg:comp_c} consists of computing a pseudo-basis for $J_i^{z_i}$ along 
with its determinantal ideal. These steps are polynomial in $K$, $l$, $d$ and $\log|\Delta|$. All we need to prove is that 
%$L$ is indeed an upper bound on $\max_{k,g,\sigma}|\sigma(\left.A_i\right._{k,g})|$ where  $\sigma:K\rightarrow\C$ runs over 
%the $d$ complex embeddings of $K$. Every $r_k$ can be written $r_k = \sum_{g\leq d}b^{(k)}_g\alpha_g$ where $(\alpha_g)_{g\leq d}$ 
%is an integral basis of $\OK$. In addition, according to~\cite[Lem. 1]{stehle_fieker_LLL}, we may assume that 
%$\|\alpha_g\|\leq \sqrt{d}2^{d^2/2}\sqrt{|\Delta|}$. Trivially, we see that our canonical choice for a representative of a 
%class modulo $\p_k$ satisfies $|b^{(k)}_g|\leq \Nm(\p_k)$. We thus have
%$$\forall \sigma,k, \ |\sigma(r_k)|\leq \|r_k\| \leq \Nm(\p_k)\sqrt{d}2^{d^2/2}\sqrt{|\Delta|}\leq N\sqrt{d}2^{d^2/2}\sqrt{|\Delta|}.$$
the coefficients of $A$, which are given by those of polynomials of the form $(y-r_k)^g$ where $g\leq l$, have a reasonable size. 
They are bounded by
$$\max_{\sigma,k,g} |\sigma(\left.A_i\right._{k,g})|\leq \binom{2l}{l}(\max_{\sigma,k}|\sigma{r_k}|)^l\leq 2^{ld^2/2}\binom{2l}{l}N^l|\Delta|^{l/2}.$$
Givem the bounds on $\|\det(A_i)\|$, we clearly see that $\g = \prod\g(J_i^{z_i})$ has bit size polynomial in $\log(N)$, $l$, $d$ 
and $\log|\Delta|$, which implies that step 9 is polynomial in all these values.

By assumption, we know the existence of $e\in\prod_i J_i^{z_i}$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} for $F$.
 We even argued in the proof of Lemma~\ref{lem:nb_pol} that we could assume 
$$\forall j\leq l, \ \|e_j\|\leq \frac{F}{(l+1)B^j}.$$
The size of the vector $e'$ corresponding to $e$ in the module $M'$ defined in Step~10 satisfies $\|e'\|\leq F/\sqrt{l+1}$, and so does the first minima $\lambda_1(M')$, that is $\lambda_1(M')\leq \|c'\| \leq  F/\sqrt{l+1}$. Note that we use $\|e\| = \sqrt{\sum_i \|e\|^2}$ to define the size of an element of an $\OK$-module. From~\cite[Th. 3]{stehle_fieker_LLL}, we know that $\Nm(\bg_1)\in[2^{-O(d^2)}, 1]$ and that 
\begin{align*}
\|x_1\| & \leq 4\cdot 2^{4d}|\Delta|^{4/d}\left(\max_{i\leq d}\|\alpha_i\|\right)^4\Nm(\bg_1)^{4/d} \\
&\leq 2^{2(1 + d(2 + d))}d^2|\Delta|^{2\left(1 + \frac{2}{d}\right)}.
\end{align*}
In addition, $\|b_1\|$ can be bounded by using~\cite[Cor. 3]{stehle_fieker_LLL}
\begin{align*}
\|b_1\| &\leq 2^{\frac{d(l+1)}{2}}\sqrt{l+1} 2^{\frac{3d}{2}}|\Delta|^{\frac{3}{2d}}\left(\max_{i\leq d}\|\alpha_i\|\right)^2\lambda_1(M')\\
&\leq 2^{d\left(\frac{l+1}{2} + \frac{3}{2} + d\right)}\sqrt{l+1}d|\Delta|^{\frac{3}{2d}}\lambda_1(M').
\end{align*}
We thus have that 
$$\|x_1b_1\|\leq \left(2^{2 + d\left(\frac{l+12}{2} + 3d\right)} d^3 |\Delta|^{2 + \frac{11}{2d}}\right)F,$$
and therefore, for every $m\in\OK$ such that $\|m\|\leq B$, the polynomial $c\in M$ corresponding to $x_1b_1\in M'$ satisfies
$$\|c(m)\|\leq \sqrt{l+1}\|x_1b_1\|\leq \sqrt{l+1}\|x_1\|\|b_1\|\leq  2^{\frac{dl}{2}}\sqrt{l+1}\left(2^{2 + d\left(6 + 3d\right)} d^3|\Delta|^{2 + \frac{11}{2d}}\right) F.$$
\end{proof}

\subsection{Good weight settings}\label{sec:weight}

To derive our main result, we need to consider weights $z_i > 0$ in $\R$ rather than $\Z$. Let 
$$\bdd := \frac{d^{3-\frac{d}{2}}2^{3\left(1 + d(2 + d)\right)}|\Delta|^{2 + \frac{11}{2d}}}{\left.\add\right.^{\frac{1}{d}}},$$
then by combining~\eqref{eq:cond_weight}, \eqref{eq:cond_F} and Algorithm~\ref{alg:comp_c}, we know that given 
$(r_1,\cdots,r_n)\in\prod_{i\leq n}\OK/\p_i$, $l>0$, $B = \prod_{i\leq k}\Nm(\p_i)$ and integer weights $z_i > 0$, 
Algorithm~\ref{alg:comp_c} returns a polynomial $c$ of degree at most $l$ such that all $m\in\OK$ satisfying $\|m\|\leq B$ and
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq &\frac{l}{2}\log(2^{d^2}B^d) + \frac{3d}{2}\log(l+1) \nonumber \\
& + \frac{1}{l+1}\sum_{i\leq n}\binom{z_i+1}{2}\log\Nm(\p_i) + \log\bdd, \label{eq:dec_cond_fin}
\end{align}
(where $a_i = 1$ if $m\bmod \p_i = r_i$, 0 otherwise) are roots of $c$. In the following, we no longer assume the 
$z_i$ to be integers. However, we will use our previous results with the integer weights $z^*_i := \lceil Az_i\rceil$ 
for a sufficently large integer $A$ to be determined.

\begin{proposition}\label{prop:dec_final}
Let $\varepsilon > 0$, non-negative reals $z_i$, $B = \prod_{i\leq k}\Nm(\p_i)$, and an encoded message 
$(r_1,\cdots,r_n)\in\prod_i\OK/\p_i$, then our algorithm finds all the $m\in\OK$ such that $\|m\|\leq B$ and 
$$\sum_{i\leq n}a_iz_i\log\Nm(\p_i)\geq \sqrt{\log(2^{d^2}B^d)\left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \varepsilon z^2_{max}\right)},$$
where $a_i = 1$ if $m\bmod \p_i = r_i$, 0 otherwise.
\end{proposition}

\begin{proof}
Note that we can assume without loss of generality that $z_{max} = 1$. Let $z^*_i = \lceil Az_i\rceil$ for a sufficently 
large integer $A$, which thus satisfies $Az_i\leq z^*_i < Az_i + 1$. The decoding condition~\eqref{eq:dec_cond_fin} is met 
whenever 
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq &\frac{l}{2A}\log(2^{d^2}B^d) + \frac{3d}{2A}\log(l+1) \nonumber \\
& + \frac{A}{2(l+1)}\sum_{i\leq n}\left(z^2_i + \frac{3}{A}z_i + \frac{2}{A^2}\right)\log\Nm(\p_i) + \frac{1}{A}\log\bdd. \label{eq:dec_cond_A}
\end{align}

Let $Z_i := z^2_i + \frac{3}{A}z_i + \frac{2}{A^2}$ for $i\leq n$ and
$$l := \left\lceil A\sqrt{\frac{\sum_{i\leq n}Z_i \log\Nm(\p_i)}{\log(2^{d^2}B^d)}}\right\rceil - 1.$$
We assume that $A\geq \log(2^{d^2}B^d)$, which ensures that $l > 0$. For this choice of $l$, condition~\eqref{eq:dec_cond_A} 
is satisfied whenever 
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq & \frac{3d}{2A}\log\left(A\sqrt{\frac{\sum_{i\leq n}Z_i \log\Nm(\p_i)}{\log(2^{d^2}B^d)}}+1\right) \nonumber \\
& + \sqrt{\log(2^{d^2}B^d)\left(\sum_{i\leq n}Z_i\log\Nm(\p_i)\right)} + \frac{1}{A}\log\bdd. \label{eq:dec_cond_l}
\end{align}
Assume that $A \geq \frac{10\log N}{\varepsilon}$ and $A\geq \frac{\log\bdd}{\log N}$, then for $N$ large enough, 
the right side of~\eqref{eq:dec_cond_l} is at most
\begin{align*}
&O\left(\frac{\log\log N}{\log N}\right) +\sqrt{\log(2^{d^2}B^d) \left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \frac{\varepsilon}{2}\right)}\\
&\leq \sqrt{\log(2^{d^2}B^d) \left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \varepsilon\right)}
\end{align*}
The degree $l$ of our decoding polynomial $c$ is therefore polynomial in $\log N$, $\frac{1}{\varepsilon}$, $d$ and $\log|\Delta|$. 
By~\cite[2.3]{ayad}, we know that the complexity to find the roots of $c$ is polynomial in $d$, $l$ and in the logarithm of the 
height of $c$, which we already proved to be polynomial in the desired values.

\end{proof}

\begin{corollary}
Let $\varepsilon > 0$, $k < n$ and prime ideals $\p_1,\cdots\p_n$ satisfying $\Nm(\p_i) < \Nm(\p_{i+1})$ and 
$\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$, then with the previous notations, our algorithm finds a list of 
all codewords which agree with a received word in $t$ places provided $t\geq\sqrt{k(n+\varepsilon)}$.
\end{corollary}

\begin{proof}
The proof is similar to the one of~\cite[Th. 7.14]{guruswami_phd}. The main difference is that we define 
$\delta := k - \frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}$ which satisfies $\delta \geq 0$ since by assumption 
$\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$. We apply Proposition~\ref{prop:dec_final} with 
$z_i = 1/\log \Nm(\p_i)$ for $i\geq k+1$, $z_i = 1/\log \Nm(\p_{k+1})$ for $i\leq k$, and 
$\varepsilon' = \varepsilon /\log\Nm(\p_{k+1})$. It allows us to retrieve the codewords whose number of agreements $t$ is at least 
\begin{align*}
&\sqrt{\frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}\left( \frac{\log(B)}{\log\Nm(\p_{k+1})} + \sum^n_{i =k+1}\frac{\Nm(\p_{k+1})}{\log\Nm(\p_i)} + \varepsilon'\right)}\\
&\leq \delta + \sqrt{\frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}\left( \frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})} + \sum^n_{i =k+1}\frac{\Nm(\p_{k+1})}{\log\Nm(\p_i)} + \varepsilon \right)}.
\end{align*}
This condition is met whenever $t\geq \delta + \sqrt{(k-\delta)(n-\delta+\varepsilon)}$. From the Cauchy-Schwartz inequality, 
we notice that 
$$\sqrt{k(n+\varepsilon)} \geq \sqrt{(k-\delta)(n-\delta+\varepsilon)},$$
which proves that our decoding algorithm works when $t\geq\sqrt{k(n+\varepsilon)}$.
\end{proof}

\section{Conclusion}

We described a polynomial time algorithm for computing the HNF basis of an $\OK$-module. Our strategy 
relies on the one of Cohen~\cite[1.4]{cohen2} who had already conjectured that his modular algorithm 
was polynomial. We made the appropriate modifications on the original algorithm and provided a 
rigorous proof of its complexity. This result is significant since other applications rely on the 
possibility of computing the HNF of an $\OK$-module in polynomial time. In particular, Fieker and Stehl{\'e}~\cite{stehle_fieker_LLL} made this assumption in the analysis of their LLL algorithms 
for $\OK$-modules. 

Our result has natural ramifications in cryptography through the LLL algorithm of Fieker and Stehl{\'e}~\cite{stehle_fieker_LLL}, but we also showed in this paper that it can be used to enhance 
the bound of the list-decoding algorithm for number field codes. We derived an analogue of the CRT list decoding algorithm for codes based on number fields which allows to 
reach the Johnson bound. We based our approach on~\cite[Ch. 7]{guruswami_phd} that provides a general 
frameworks for list decoding of algebraic codes. 
%We followed the approach of~\cite[Ch. 7]{guruswami_phd} that provides a general 
%frameworks for list decoding of algebraic codes, along with its application to CRT codes. The modifications to 
%make this strategy efficient in the context of number fields are substantial. We needed to refer to the theory of 
%modules over a Dedekind domain, and carefully analyse the process of intersecting them, as well as finding a short basis. 
%Our algorithm is polynomial in $d$, $\log(N)$ and in $\log|\Delta|$. The only regret we can have is that we need to 
%assume $\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$, which is the only difference with the result 
%of~\cite[Ch. 7]{guruswami_phd} on CRT codes.

%We could not conclude on whether the numer field codes can allow better decoding settings than CRT codes. So far, 
%we have shown that they were effective and at least as good as CRT codes. Other types of decoding could be tried. 
%In addition, more fundamental questions could be raised, for example on the performances of the dual code of a number field code. 


\bibliography{paper}


\end{document}
